Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 136 - Ugly numbers / 136.2.cpp
bloba18af46afdb7e7baf68c0ead180abd29b6081d5e
1 using namespace std;
2 #include <algorithm>
3 #include <iostream>
4 #include <iterator>
5 #include <numeric>
6 #include <sstream>
7 #include <fstream>
8 #include <cassert>
9 #include <climits>
10 #include <cstdlib>
11 #include <cstring>
12 #include <string>
13 #include <cstdio>
14 #include <vector>
15 #include <cmath>
16 #include <queue>
17 #include <deque>
18 #include <stack>
19 #include <list>
20 #include <map>
21 #include <set>
23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
25 #define D(x) cout << #x " is " << x << endl
27 int main(){
28 vector<long long> ugly;
29 ugly.push_back(1);
31 priority_queue<long long, vector<long long>, greater<long long> > q;
32 q.push(1);
34 while (ugly.size() < 1500) {
35 long long v = q.top();
36 q.pop();
37 if (ugly.back() != v) {
38 ugly.push_back(v);
40 if (v % 3 != 0 and v % 5 != 0) {
41 q.push(v * 2);
44 if (v % 5 != 0) {
45 q.push(v * 3);
47 q.push(v * 5);
49 // for (int i = 0; i < 100; ++i) {
50 // printf("ugly[%d] = %lld\n", i, ugly[i]);
51 // }
52 printf("The 1500'th ugly number is %lld.\n", ugly[1499]);
54 return 0;